//
// test.go
// Copyright (C) 2019 crane <crane@his-pc>
//
// Distributed under terms of the MIT license.
//

/*
 * 题目描述:
 *   查找一个数组的首次连续子数组, 要求这个子数组是连续的, 并且是长度是contin_len, 返回这个子数组的最后一个元素的在原数组的索引位置.
 *   void find_contin(int* int_arr, int tatol_len, int contin_len, int& out_end);
 *
 *   1 3 5 7 2  11  9  4  3  2  5  6  1  7  9  8 返回连续5个元素的子数组, 那么4就是, 下标为7
 *
 *   1 3 5 7 2  11  9  4 这里面有1,2, 3,4,5 就满足子数组条件了
 */

package main

import (
	"fmt"
)

type UnionFindSet struct {
	parent map[int]int
}

func NewUnionFindSet() *UnionFindSet {
	return &UnionFindSet{
		parent: make(map[int]int),
	}
}

func (u *UnionFindSet) FindParentOf(value int) int {
	cur := value
	cur_p := value
	ok := false

	fmt.Println("find", value)
	if cur_p, ok = u.parent[value]; !ok {
		// 如果不存在, 返回自身. 自己独成一派!
		return cur
	}

	// 如果没有找到UnionSet的根部, 继续find, 直到找到根部(value == value.parent)
	for cur != cur_p {
		u.parent[cur] = cur_p // 压缩路径

		cur = cur_p
		//cur_p = u.parent[cur_p]
		cur_p = u.FindParentOf(cur_p)
	}

	fmt.Println("find2", value, cur_p)
	return cur_p
}

func (u *UnionFindSet) Connect(parent int, value int) int {
	ancestor := u.FindParentOf(parent)
	u.parent[value] = ancestor
	fmt.Println("after connect", value, "---->", ancestor)
	return ancestor
}

func (u *UnionFindSet) Has(value int) bool {
	_, ok := u.parent[value]
	return ok
}

// 算法题目:
func find_first_match_continuous_set(array []int, match_count int) int {
	u := NewUnionFindSet()
	for idx, value := range array {

		// 尝试连接当前value和value-1
		parent := 0
		if u.Has(value - 1) {
			parent = u.Connect(value-1, value)
		} else {
			parent = u.Connect(value, value)
		}

		if value-parent+1 >= match_count {
			return idx
		}

		// 尝试连接当前value和value+1
		if u.Has(value + 1) {
			match_value := parent + match_count - 1
			if u.Has(match_value) && u.FindParentOf(match_value) == value+1 {
				return idx // 因为当前value的加入, 连接了value-1之前的值 和 value+1 之后的值
			}

			// 合并前后并查集
			u.Connect(value, value+1)
		}
	}

	return -1

}

// func test() {
// 	u := NewUnionFindSet()
// 	a := []int{1, 2, 3, 4}

// 	for idx, e := range a {
// 		u.Connect(e, e)

// 		if idx != 0 {
// 			// fmt.Println("conn", e-1, e)
// 			u.Connect(e-1, e)
// 		}
// 	}

// 	// fmt.Println(100, u.FindParentOf(100))
// 	for _, e := range a {
// 		if u.FindParentOf(e) != 1 {
// 			panic("Logic error, Please check your UnionFindSet code!")
// 		}

// 	}

// }

func algo() {
	nums := []int{1, 3, 5, 7, 2, 11, 9, 4, 3, 2, 5, 6, 1, 7}
	ret := find_first_match_continuous_set(nums, 5)
	// fmt.Println(ret)
	if ret != 7 {
		panic("Algorithm logic error")
	}

	nums = []int{1, 2, 3, 4, 5, 100, 6, 7}
	ret = find_first_match_continuous_set(nums, 7)
	// fmt.Println(ret)
	if ret != 7 {
		panic("Algorithm logic error")
	}

	nums = []int{1, 3, 2, 4, 100, 5}
	ret = find_first_match_continuous_set(nums, 5)
	// fmt.Println(ret)
	if ret != 5 {
		panic("Algorithm logic error")
	}

	nums = []int{1, 3, 2, 4, 100, 101, 5}
	ret = find_first_match_continuous_set(nums, 5)
	// fmt.Println(ret)
	if ret != 6 {
		panic("Algorithm logic error")
	}

	nums = []int{99, 1, 3, 98, 2, 4, 100, 101, 5}
	ret = find_first_match_continuous_set(nums, 5)
	if ret != 8 {
		panic("Algorithm logic error")
	}

}

func main() {
	fmt.Println("start main")
	// test()
	algo()
}
